package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 数组中的第K个最大元素  ,自己写的快排超时了
 * 注意点:   43和50行用while循环， 36行，先做返回判断再取40行的值，不然会越界，59，60要形成递归
 * @date 2022/9/30 16:18
 */
public class Demo40 {
    public static void main(String[] args) {

    }

    public int findKthLargest(int[] nums, int k) {
        //长度小于1,直接返回
        if(nums.length<1){
            return 0;
        }
        //自己写个快排
        quickSort(nums);
        return  nums[nums.length-k];
    }

    private static void quickSort(int[] nums) {
        //长度小于1,直接返回
        if(nums.length<=1){
            return;
        }
        //长度大于1
        sort(nums,0,nums.length-1);

    }

    private static void sort(int[] nums, int left, int right) {
        //先做返回判断
        if(left>=right){
            return;
        }
        int mid=nums[left];
        int start=left;
        while (left<right){
            //用while
            while (mid <nums[right]&&left<right) {
                right--;
            }
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            //用while
            while (mid >=nums[left]&&left<right) {
                left++;
            }
            int temp1=nums[right];
            nums[right]=nums[left];
            nums[left]=temp1;
        }
        nums[left]=mid;
        sort(nums,start,left-1);
        sort(nums,left+1,nums.length-1);
    }
}
